#
# @lc app=leetcode.cn id=647 lang=python3
#
# [647] 回文子串
#

# @lc code=start
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        cnt = 0
        # dp[i][j] = dp[i+1][j-1]
        # i从大到小循环
        for i in range(n-1, -1, -1):
            # j从小到大循环
            for j in range(i, n):
                if s[i]==s[j]:
                    if j-i<=2:
                        dp[i][j]=True
                    elif j-i>=3:
                        dp[i][j]=dp[i+1][j-1]
                    if dp[i][j]:
                        cnt+=1
                
        return cnt
                

# @lc code=end

